package com.acwing.partition9;

import java.io.*;

/**
 * @author `RKC`
 * @date 2021/12/4 14:19
 */
public class AC874筛法求欧拉函数 {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = reader.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        writer.write(eulerSum(n) + "\n");
        writer.flush();
    }

    private static long eulerSum(int n) {
        int[] primes = new int[n + 1], euler = new int[n + 1];
        int count = 0;
        boolean[] isNotPrime = new boolean[n + 1];
        euler[1] = 1;
        for (int i = 2; i <= n; i++) {
            if (!isNotPrime[i]) {
                primes[count++] = i;
                //如果i是质数，那么它的欧拉函数就是i-1，也就是2到i-1的所有数都和i互质
                euler[i] = i - 1;
            }
            for (int j = 0; primes[j] <= n / i; j++) {
                isNotPrime[primes[j] * i] = true;
                if (i % primes[j] == 0) {
                    //此时primes[j]是i的一个质因子，因为euler[i]=i(1-1/p1)...(1-1/pk)；
                    //又因为primes[j]是primes[j]*i的质因子，所以euler[primes[j]*i]=primes[j]*i(1-1/p1)...(1-1/pk)；
                    //而primes[j]*euler[i]=primes[j]*i(1-1/p1)...(1-1/pk)
                    //所以primes[j]*euler[i]=primes[primes[j] * i]
                    euler[primes[j] * i] = euler[i] * primes[j];
                    break;
                }
                //当primes[j]不是i的质因子时，euler[i]=i(1-1/p1)...(1-1/pk)；euler[primes[j] * i]=primes[j] * i(1-1/p1)...(1-1/pk)*(1-1/primes[j])
                //将euler[i]代入得euler[primes[j] * i]=primes[j] * euler[i] * (1-1/primes[j]) => euler[primes[j] * i]=euler[i](primes[j] - 1)
                euler[primes[j] * i] = euler[i] * (primes[j] - 1);
            }
        }
        long answer = 0;
        for (int i = 1; i <= n; i++) answer += euler[i];
        return answer;
    }
}
